[Coding015] LeetCode 23

Merge k Sorted Lists

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

2的幂次是一个很有意思、且值得深入研究的一个问题。

• pace = 1;

• i = i + pace * 2;

• [i, i + pace]

• pace = pace * 2;

题目：23. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

xxxxxxxxxx
10
1
Input: lists = [[1,4,5],[1,3,4],[2,6]]
2
Output: [1,1,2,3,4,4,5,6]
3
Explanation: The linked-lists are:
4
[
5
  1->4->5,
6
  1->3->4,
7
  2->6
8
]
9
merging them into one sorted list:
10
1->1->2->3->4->4->5->6

Example 2:

xxxxxxxxxx
2
1
Input: lists = []
2
Output: []

Example 3:

xxxxxxxxxx
2
1
Input: lists = [[]]
2
Output: []

Constraints:

• k == lists.length

• 0 <= k <= 104

• 0 <= lists[i].length <= 500

• -104 <= lists[i][j] <= 104

• lists[i] is sorted in ascending order.

• The sum of lists[i].length will not exceed 104.

代码1（配 · 手绘过程图）

xxxxxxxxxx
32
1
class Solution {
2
    
3
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
4
        ...
5
    }
6

7
    public ListNode mergeKLists(ListNode[] lists) {
8

9
        int n = lists.length;
10
        if (n == 0) return null;
11

12
        int pace = 1;
13

14
        while (pace < n)
15
        {
16
            // 上：i = 0;
17
            // 下：i = i + pace * 2
18
            
19
            // 注意 i + pace < n; 
20
            // 注意 i = i + pace * 2
21
            for (int i = 0; i + pace < n; i = i + pace * 2) 
22
            {
23
                // 左边： list[i]
24
                // 右边： list[i + pace]
25
                lists[i] = mergeTwoLists(lists[i], lists[i + pace]);  // i + pace
26
            }
27
            pace = pace * 2;  // 累乘
28
        }
29

30
        return lists[0];
31
    }
32
}

代码解读

本题有两个弯弯绕的地方：

❶ 每次循环的时候，循环体本身的i是如何变化的？ 循环体内部的i又有什么作用？

• 循环体内，(MergeTwoLists简写为M)，每次合并的对象M(i, i + xx);

• 循环体，for (i = 0; i ... ; i = i + yy)

❷ pace的变化，是如何实现2路、4路、8路归并的？

复杂度分析

while循环的时间复杂度（Time complexity）：$O(logk)$$O(logk)$, $k$$k$ is the number of linked lists.

for循环内，就是把所有链表中的numbers整合在一起，如果所有numbers的数量是$n$$n$，那么for循环的时间复杂度是$O(n)$$O(n)$

所以，合并起来是：$O(nlogk)$$O(nlogk)$

附：功能代码（合并两个有序链表）

xxxxxxxxxx
45
1
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
2
        // 基本情况的判定
3
        if (list1 == null && list2 == null) return null;
4
        if (list1 == null) return list2;
5
        if (list2 == null) return list1;
6

7
        // 结果链表，最后返回的是：dummy.next; (经典操作)
8
        ListNode dummy = new ListNode(0);
9
        // 让r指向dummy，这样就让r冲锋中前，dummy稳坐军营即可！
10
        ListNode r = dummy;
11

12
        // p, q分别作为指针操作待合并的两个链表
13
        ListNode p = list1;
14
        ListNode q = list2;
15

16
        // 如果都还不为空的时候，就开始一个一个比较；
17
        while (p != null && q != null)
18
        {
19
            if (p.val <= q.val)
20
            {
21
                r.next = p;
22
                p = p.next;
23
            }
24
            else
25
            {
26
                r.next = q;
27
                q = q.next;
28
            }
29
            r = r.next;
30
        }
31

32
        // 如果有一个已经完全插入到结果链表，而另一个还剩点尾巴的时候，直接接上
33
        if (p != null)
34
        {
35
            r.next = p;
36
        }
37

38
        if (q != null)
39
        {
40
            r.next = q;
41
        }
42

43
        return dummy.next;
44
    }
45

★ 知识点积累 (Java)

1. 原本想使用$2^x$$2^x$这样的形式来实现2的幂次计算。

   pow() 方法用于返回第一个参数的第二个参数次方。

   语法

   xxxxxxxxxx
   1
   1
   double pow(double base, double exponent)
   

   Demo: $2^x$$2^x$

   xxxxxxxxxx
   1
   1
   int res = (int)Math.pow(2, x);
   

   参数

   • base -- 任何原生数据类型。

   • exponent -- 任何原生数据类型。

   但是发现，这个发现返回值是double，没法作为下标来索引数组的元素。所以放弃了。

   （放弃的另一个原因还有，for循环体条件中i变化，和for循环内对i参数的变化，相差了一个2倍，不太好控制具体的变化，后来发现用累乘方式实现比较科学，所以放弃了原有的代码）

    

   ---

    

   复杂代码如下（同样可以提交通过）

   xxxxxxxxxx
   18
   1
   public ListNode mergeKLists(ListNode[] lists) {
   2
   
   3
           int n = lists.length;
   4
           if (n == 0) return null;
   5
   
   6
           int pace = 1;
   7
   
   8
           while ((int)Math.pow(2, pace - 1) < n)
   9
           {
   10
               for (int i = 0; i + (int)Math.pow(2, pace - 1) < n; i = i + (int)Math.pow(2, pace))
   11
               {
   12
                   lists[i] = mergeTwoLists(lists[i], lists[i + (int)Math.pow(2, pace - 1)]);
   13
               }
   14
               pace = pace + 1;
   15
           }       
   16
   
   17
           return lists[0];
   18
       }